In many applications in binary arithmetic, one requires a device, called a full adder (FA), which receives three digital signals and then computes the binary representation of the number of high signals among the three signals. Further, it is often advantageous to design the device so that the delay in the computation is much smaller for one of the three signals than for the other two. This is typically achieved by performing the computation in two stages, the first involving only two of the signals, the second involving the third signal and the result of the first stage. We refer to the third signal as the carry-in.
In one implementation of the device pass-gates are used, as these are typically faster than standard CMOS gates. When designing the circuit to conform to a standard-cell methodology, however, pass-gates pose one disadvantage: A FA standard cell must be characterisable, which is to say that it must have a well defined input capacitance and output impedance. On their own, pass-gates are not characterisable; two of the input/output pins, corresponding to the source and drain terminals of the pass-gate, do not have a well defined input capacitance. As a result, these pins are not normally permitted to be connected directly to the input/output pins of the standard cell. This constraint often results in a design which is not as fast as it might be.
The following notation is used for logical operations on Boolean variables (such that take one of two values, high and low):                a b denotes the AND of a and b, which is high if a and b are high.        a+b denotes the OR of a and b, which is high if a is high or b is high.        a⊕b denotes the exclusive OR of a and b, which is high if a and b have different values.        a-bar is the complement of a, which is high if a is low.        Σi=a i=b S(i) denotes the OR of a plurality of Boolean expressions, i.e. S(a)+S(a+1)+ . . . +S(b).        
A prior-art FA circuit, at the level of Boolean logic, is shown in FIG. 1. This is an efficient way to build a FA with a fast carry-in (CIN). The circuit has three inputs, A, B and CIN, and two outputs S and C.
Output S represents a sum bit in the addition of A, B and CIN, and S is the logical XOR of inputs A, B and CIN, i.e. S=A⊕B⊕CIN. S is high if an odd number of A, B and CIN are high and is low if an even number are high.
Output C represents an output carry bit from the addition of A, B and CIN. C is high if at least two of A, B and CIN are high, otherwise C is low.
The circuit comprises an XOR gate 100 with inputs A and B and an output A⊕B. A second XOR gate 110 has inputs A⊕B (from the first XOR gate 100) and CIN, and an output S. A multiplexer (mux) 120 has A⊕B as a select input, B (or equivalently A) as a “0” input, and CIN as a “1” input and gives C as an output. C is equal to A if A⊕B is low; C is equal to CIN if A⊕B is high.
A prior-art implementation of the circuit of FIG. 1, using pass-gates, is shown in FIG. 2. Again, the circuit has inputs A and B, a carry input CIN, a carry output C and a sum output S.
The first XOR gate 100 is implemented using pass gates 204, 205, 206 and 207. These pass gates actually work in pairs to form two XOR gates, one of which generates A⊕B using pass gates 206 and 207, and the other of which generates the complement of A⊕B using pass gates 204 and 205. The second XOR gate 110 is implemented using pass gates 215 and 216. The multiplexer 120 is implemented using pass gates 213 and 214.
Input A is connected to the input of an inverter 202. The output of this inverter 202 is connected to the source terminal of pass gates 204 and 207. The output of inverter 202 is also connected to the input of a further inverter 203. The output of inverter 203 is connected to the source terminal of pass gates 205 and 206.
Input B is connected directly to the gate terminals of pass gates 205 and 207, and to the inverse gate terminals of pass gates 204 and 206. Input B is also connected to the input of inverter 201. The output of inverter 201 is connected to the gate terminals of pass gates 204 and 206, and to the inverse gate terminals of pass gates 205 and 207. The output of inverter 201 is also connected to the source terminal of pass gate 214.
Pass gates 206 and 207 and inverters 201, 202 and 203 function as an XOR gate, to generate the function A⊕B. The drain outputs of pass gates 206 and 207 are connected together to give a A⊕B output.
Only one of pass gates 206 and 207 is switched on at the same time, because pass gate 206 receives the opposite control signal on its gate terminals to that received by pass gate 207, due to the order of connection of the B input and the inverted B input to the gate terminals. Pass gate 206 is switched on only if B is low, but pass gate 207 is switched on only if B is high. Thus, if B is low, the signal passed by pass gate 206 is from the A input, but if B is high, the signal passed by pass gate 207 is from the inverted A input. By this means, the XOR function is performed.
Pass gates 204 and 205 and inverters 201, 202 and 203 also function as an XOR gate, but they generate the complement of the function A⊕B. The drain outputs of pass gates 204 and 205 are connected together to give a (A⊕B)-bar output, represented on the figure as AxorBbar.
Only one of pass gates 204 and 205 is switched on at the same time, because pass gate 204 receives the opposite control signal on its gate terminals to that received by pass gate 205, due to the order of connection of the B input and the inverted B input to the gate terminals. Pass gate 204 is switched on only if B is low, but pass gate 205 is switched on only if B is high. Thus, if B is low, the signal passed by pass gate 204 is from the inverted A input, but if B is high, the signal passed by pass gate 205 is from the A input.
The drain outputs of pass gates 206 and 207 are connected to the gate terminals of pass gates 213 and 215 and the inverse gate terminals of pass gates 214 and 216, providing the A⊕B signal at these terminals. The drain outputs of pass gates 204 and 205 are connected to the gate terminals of pass gates 214 and 216 and the inverse gate terminals of pass gates 213 and 215, providing the (A⊕B)-bar signal at these terminals.
The carry input CIN is connected to the input terminal of inverter 211. The output of inverter 211 is connected to the source inputs of pass gates 213 and 216. The output of inverter 211 is also connected to the input of inverter 212. The output of inverter 212 is connected to the source input of pass gate 215. The source input of pass gate 214 is connected to the output of inverter 201, to receive a signal of not-B.
The pass gates 215 and 216 act together as an XOR gate to generate an output sum bit S. The drain outputs of pass gates 215 and 216 are connected together, and are connected to the input of inverter 218.
The pass gates 215 and 216 are switched by the A⊕B and (A⊕B)-bar outputs of the pass gates 204–207 in the first part of the circuit. When A⊕B is high, pass gate 215 is switched on, and the CIN signal is passed through to inverter 218, where it is inverted to generate not-CIN. When A⊕B is low, pass gate 216 is switched on, and the not-CIN signal is passed through to inverter 218, where it is inverted to generate not-CIN. In other words, the sum bit S is only high if only one of A, B and CIN, or all three of A, B and CIN is high.
The pass gates 213 and 214 act together as a multiplexer to generate a carry output bit C. The drain outputs of pass gates 213 and 214 are connected together, and are connected to the input of inverter 217.
The pass gates 213 and 214 are switched by the A⊕B and (A⊕B)-bar outputs of the pass gates 204–207 in the first part of the circuit. When A⊕B is high, pass gate 213 is switched on, and the not-CIN signal is passed through to inverter 217, where it is inverted to generate CIN. When A⊕B is low, pass gate 214 is switched on, and the not-B signal is passed through to inverter 217, where it is inverted to generate B. In other words, the carry output bit C is only high if at least two of A, B and CIN are high.
Since the implementation conforms to the standard-cell methodology, no pass-gate source or drain connection is connected to either an input pin or an output pin. As a result, the critical path from CIN to the outputs, along which signals take the longest time to propagate, passes through a total of three inverters 211, 212 and 218 and a pass-gate 215.